
#include <hash.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

unsigned int _hash(char *key, unsigned int len){

  static int hash_bytes = sizeof(unsigned int);
  unsigned int hash = 0xf63d1e1; // Some random num I made up.
  char *hash_ptr = (char *)&hash;
  
  int i = 0;
  for ( ; i < len; i++){
    int j = 0;
    for ( ; j < hash_bytes; j++){
      hash_ptr[j] = key[i] ^ (hash_ptr[j]);
    }
  }

  return hash;

}

hash_t *hash_new(unsigned int capacity){

  hash_t *table = (hash_t *)malloc(sizeof(hash_t));
  table->space = capacity;
  table->entries = 0;
  
  table->table = (hash_elem *)malloc(sizeof(hash_elem) * capacity);
  memset(table->table, 0, sizeof(hash_elem) * capacity);

  return table;

}

hash_key *hash_new_key(void *data, unsigned int length){

  /* Make the library's copy of the data. */
  void *libs_data = malloc (length);
  memcpy(libs_data, data, length);
  
  hash_key *new_key = (hash_key *) malloc(sizeof(hash_key));
  new_key->key = libs_data;
  new_key->length = length;
  new_key->hash = _hash(data, length);

  return new_key;

}

hash_elem *hash_new_elem(hash_key *key, void *data){

  hash_elem *new_elem = (hash_elem *) malloc(sizeof(hash_elem));
  new_elem->key = key;
  new_elem->data = data;

  return new_elem;

}

hash_iterator *hash_new_iterator(hash_t *hash){

  hash_iterator *i = (hash_iterator *)malloc(sizeof(hash_iterator));
  i->table = hash;
  i->offset = 0;

  return i;

}

/**
 * Iterates over a table returning the next used elem in the sequence.
 */
hash_elem *hash_iterate(hash_iterator *i){

  for ( ; i->offset < i->table->space; i->offset++){
    if ( i->table->table[i->offset].used){
      return &(i->table->table[i->offset++]);
    }
  }

  return NULL;

}

/**
 * Probes for an open space or collided key quadratically.
 */
int _hash_lin_probe(hash_t *tbl, int seed){

  int i = 0;
  for ( ; i < tbl->space; i++){
    if (!tbl->table[(seed + i) % tbl->space].used){
      /* We have a free elem. */
      return (seed + i) % tbl->space;
    }
  }

  return -1;

}


/**
 * This special add function should only be used by the hash_expand_table()
 * function.
 */
void _hash_add(hash_t *tbl, hash_elem *elem){

  unsigned int offset = elem->key->hash % tbl->space;

  //printf("hash:0x%08x offset:%u\n", elem->key->hash, offset);

  if (tbl->table[offset].used){
    //printf("[_hash_add] Ahhh, collision.\n");
    unsigned int good_offset = _hash_lin_probe(tbl, (int) offset);
    memcpy(&(tbl->table[good_offset]), elem, sizeof(hash_elem));
  } else {
    memcpy(&(tbl->table[offset]), elem, sizeof(hash_elem));
  }

  tbl->entries++;

}

void _hash_expand_table(hash_t *tbl){

  hash_t *new_tbl = hash_new(tbl->space * LOAD_INCREASE);

  /* Iterate over the old table and pull the keys/elems out. */

  int i = 0;
  for ( ; i < tbl->space; i++){
    if (tbl->table[i].used){
      /* Copy this elem over to the new table. */
      _hash_add(new_tbl, &(tbl->table[i]));
    }
  }

  /* Finally, clean up. */
  free(tbl->table);
  memcpy(tbl, new_tbl, sizeof(hash_t));
  free(new_tbl);

}

hash_t *hash_add(hash_t *tbl, void *key, unsigned int key_len, void *data){

  /* First see if this add will make the load of the table increase to be */
  /* larger than the load factor. If it is make the table bigger.         */
  float hash_load = (float) tbl->entries / tbl->space;
  if (hash_load > LOAD_FACT){
    _hash_expand_table(tbl);
  }

  /* First make a hash_elem. */
  hash_elem *new_elem = hash_new_elem(hash_new_key(key, key_len), data);
  new_elem->used = 1;

  /* Determine where it goes. */
  unsigned int offset = new_elem->key->hash % tbl->space;

  /* Check if the space is taken already. */
  if (tbl->table[offset].used){
    /* We have to find another place nearby. */
    offset = _hash_lin_probe(tbl, (int) offset);
    memcpy(&(tbl->table[offset]), new_elem, sizeof(hash_elem));
  } else {
    /* Just put the elem in. */
    memcpy(&(tbl->table[offset]), new_elem, sizeof(hash_elem));
  }

  tbl->entries++;
  free(new_elem);
  return tbl;

}

int _hash_cmp_key(hash_key *k1, hash_key *k2){

  if (k1->hash != k2->hash) return 1;
  if (k1->length != k2->length) return 1;

  return memcmp(k1->key, k2->key, k1->length);

}

hash_elem *hash_get_elem(hash_t *tbl, hash_key *key){

  /* Make our first guess for the offset. */
  unsigned int offset = key->hash % tbl->space;
  //fprintf(stderr, 
	  //"[_hash_get] offset guess: %u hash: 0x%08x\n", offset, key->hash);

  /* We will linearly probe for the first elem with a matching key. */
  int i = 0;
  for ( ; i < tbl->space; i++){
    hash_key *test = tbl->table[(offset + i) % tbl->space].key;
    if (!test) continue;
    //fprintf(stderr, "[_hash_get] key hash: 0x%08x\n", test->hash);
    if (!_hash_cmp_key(test, key)){
      //fprintf(stderr, "Returning the found elem.\n");
      return &(tbl->table[(offset + i) % tbl->space]);
    }
  }

  //fprintf(stderr, "Found no matching keys.\n");

  return NULL;

}

hash_elem *hash_get(hash_t *tbl, void *key, unsigned int length){

  hash_key *tmp_key = hash_new_key(key, length);
  if (!tmp_key){
    return NULL;
  }

  hash_elem *elem = hash_get_elem(tbl, tmp_key);

  free(tmp_key);
  return elem;

}

hash_elem *_hash_remove_elem(hash_t *tbl, hash_elem *elem){

  if (!elem){
    return NULL;
  }

  hash_elem *removed = (hash_elem *) malloc(sizeof(hash_elem));
  memcpy(removed, elem, sizeof(hash_elem));
  removed->used = 0;

  memset(elem, 0, sizeof(hash_elem));
  return removed;

}

hash_elem *hash_remove_key(hash_t *tbl, hash_key *key){

  return _hash_remove_elem(tbl, hash_get_elem(tbl, key));

}

hash_elem *hash_remove(hash_t *tbl, void *key, unsigned int length){

  return _hash_remove_elem(tbl, hash_get(tbl, key, length));

}

/** Print the table. This is useful for debugging. **/
void hash_print(hash_t *tbl){

  printf("Hashtable: space=%d entries=%d load:%f\n", 
	 tbl->space, tbl->entries, (float) tbl->entries / (float) tbl->space);
  int i = 0;
  for ( ; i < tbl->space; i++){
    printf("  Entry (%d): hash:0x%08x data_addr:0x%08lx used:%d\n", i, 
	   tbl->table[i].key != NULL ? tbl->table[i].key->hash : 0,
	   (long unsigned int)tbl->table[i].data, tbl->table[i].used);
  }

}

void hash_print_key(hash_key *key){

  printf("Key: data: ");
  int i = 0;
  for ( ; i < key->length; i++){
    printf("%d ", ((char *)key->key)[i]);
  }
  printf("\n  hash=0x%08x\n", key->hash);

}

void hash_print_elem(hash_elem *elem){

  printf("Elem: used=%d data=0x%08lx\n", elem->used, 
	 (long unsigned int) elem->data);
  hash_print_key(elem->key);

}
